package QuestionDaily;

public class maxScore_1423 {
    /**
     * 每次从数组左边或右边取一个数字。一共取k个数字
     * 求这些数的最大和
     */
    public int maxScore(int[] cardPoints, int k) {
        /**
         * 想法是用一个数组 arr[i]，记录左边取 i 个数时，右边取k-i个数字时的数字和
         * 同时进行动态规划，记录左边取 i 个数字时这部分数字和
         * 以及右边取i个数字时这部分数字和
         * 2ms
         * 哥们现在真的nb了
         */
        int len=cardPoints.length;
        int sumLeft[]=new int[k+1];
        int sumRight[]=new int[k+1];
        //初始化sumLeft和sumRight，方便后边计算
        for(int i=1;i<=k;i++){ //从1开始遍历
            sumLeft[i]=cardPoints[i-1]+sumLeft[i-1];
            sumRight[i]+=cardPoints[len- i]+sumRight[i-1];
        }
        int max=0;
        for(int i=0;i<=k;i++){
            int sum = sumLeft[i] + sumRight[k - i];
            if(sum >max)
                max= sum;
        }
        return max;
    }
}
